package Offer31;

import java.util.Stack;

/**
 * @author 23737
 * @time 2021.9.24
 * 栈的压入和弹出操作：
 * 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。
 * 例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
 * <p>
 *  
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Test {
    public static void main(String[] args) {
        int[] a = new int[]{1, 2, 3, 4, 5};
        int[] b = new int[]{4, 3, 5, 2, 1};
        System.out.println(new Solution().validateStackSequences(a, b));
    }
}

/*
个人题解：使用一个栈来模拟入栈的过程，然后再来
使用一个挂来摸拟压入弹出操作。每次入栈一个元素后，都要井断一下榄顶元素是不是当前出接序列lpopSequence的第一个元素。
如果是的话风做行出核操作并将 popecvence往后移一位，继续进行判断。
*/
class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        if (pushed.length == 0 || popped.length == 0) {
            return true;
        }
        //首先用一个变量将入栈的数组的长度进行存储
        int n = pushed.length;
        //用栈来模拟数组入栈的过程
        Stack<Integer> stack = new Stack<>();
        for (int pushIndex = 0, popIndex = 0; pushIndex < n; pushIndex++) {
            stack.push(pushed[pushIndex]);
            //!!!这里是一个坑！必须注意，stack.peek() == popped[popIndex]的判断一定要写在第三个上，不然因为栈空了之后就会报出异常而不会继续运行！
            while (popIndex < n && !stack.isEmpty() && stack.peek() == popped[popIndex]) {
                stack.pop();
                popIndex++;
            }
        }
        return stack.isEmpty();
    }
}

/*官方题解*/
class SolutionTwo {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int N = pushed.length;
        Stack<Integer> stack = new Stack();

        int j = 0;
        for (int x: pushed) {
            stack.push(x);
            while (!stack.isEmpty() && j < N && stack.peek() == popped[j]) {
                stack.pop();
                j++;
            }
        }

        return j == N;
    }
}


